package Algorithm.Dp;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class Leetcode85 {
    /**
     * 使用 DP 的思想，0 变成一个负数，然后求最大和
     */
    class Solution {
        public int maximalRectangle(char[][] matrix) {
            if(matrix==null||matrix.length==0)
                return 0;
            int max = matrix[0][0] - '0';

            for(int i=0;i<matrix.length;i++){
                int[] sum = new int[matrix[0].length];
                for(int j=i;j<matrix.length;j++){
                    int ss = 0;

                    for(int k=0;k<matrix[i].length;k++){
                        if(matrix[j][k]=='0'){
                            sum[k] = Integer.MIN_VALUE;
                        }else{
                            sum[k] += matrix[j][k] - '0';
                        }

                        if(sum[k]>0){
                            ss = Math.max(ss + sum[k], sum[k]);
                            max = Math.max(ss,max);
                        }else{
                            ss = sum[k];
                        }

                    }
                }
            }

            return max;
        }
    }

    /**
     * 把问题转换成 从柱状图中找出最大矩形的问题，利用单调栈解决
     */
    class Solution2 {
        public int maximalRectangle(char[][] matrix) {
            int[][] sums = new int[matrix.length][matrix[0].length];

            Deque<Integer> stack = new LinkedList<Integer>();
            int[] left;
            int[] right;
            int max = 0;
            for(int i=0;i<sums.length;i++){
                stack.clear();
                left = new int[sums[i].length];
                right = new int[sums[i].length];
                Arrays.fill(right, sums[i].length);
                for(int j=0;j<sums[i].length;j++){
                    //如果当前位置是1，那么就是把上行的值+1，否则是0
                    if(i!=0){
                        sums[i][j] = matrix[i][j] == '1' ? sums[i-1][j] + 1 : 0;
                    }else{
                        sums[i][j] = matrix[i][j] == '1' ? 1 : 0;
                    }

                    //弹出栈中大于等于当前值的数，并且设置弹出的值的右边界
                    while(!stack.isEmpty() && sums[i][stack.peek()] >= sums[i][j]){
                        int index = stack.pop();
                        right[index] = j;
                    }

                    //设置当前值的左边界
                    left[j] = stack.isEmpty()?-1:stack.peek();
                    stack.push(j);
                }

                for(int k=0;k<left.length;k++){
                    max = Math.max(max, ((right[k] - left[k] - 1) * sums[i][k]));
                }
            }

            return max;
        }
    }

}
